import numpy as np
import pandas as pd
from collections import Counter, defaultdict
import string
import plotly.express as px
import plotly.offline as py
from plotly.subplots import make_subplots
import plotly.graph_objects as go
from typing import Dict
from scipy.stats import norm
from tqdm import tqdm
from IPython.display import clear_output

cyrillic_alphabet = set('абвгдеёжзийклмнопрстуфхцчшщъыьэюя')
ascii_alphabet = set(string.ascii_lowercase)
print(f'cyrillic_alphabet={sorted(list(cyrillic_alphabet))}')
print(f'ascii_alphabet={sorted(list(ascii_alphabet))}')

cyrillic_alphabet=['а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я', 'ё']
ascii_alphabet=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

Вспомогательные функции

def read_file(filename):
    with open(filename, 'r') as fn:
        return fn.read()
    
def clear_text(text, alphabet, add_space=True):
    permitted_chars = alphabet
    if add_space:
        permitted_chars = set(alphabet) | {" "}
    return ''.join(x for x in text.lower() if x in permitted_chars)
    
def count_n_grams(text, n=1):
    counter = Counter()
    for start in range(0, len(text) - n + 1):
        counter.update([text[start : start+n]])
    return counter

def read_corpus(filename, alphabet, n_gram_size=1, add_space=True):
    text = read_file(filename)
    text = clear_text(text, alphabet, add_space)
    return count_n_grams(text, n_gram_size)

def corpus_to_df(corpus):
    df = pd.DataFrame([dict(char=k, count=v) for k,v in corpus.items()])
    total_num = float(sum(corpus.values()))
    df['count'] /= total_num
    return df.sort_values('char')

def generate_samples(filename, alphabet, min_len, max_len, number_of_samples, add_space=True):
    sample = read_file(filename)
    sample = [clear_text(x, alphabet, add_space) for x in sample.split('\n')]
    sample = [x for x in sample if min_len <= len(x) <= max_len]
    return np.random.choice(sample, number_of_samples)

def permutate(sample):
    chars = list(set(sample))
    original_chars = list(set(sample))
    np.random.shuffle(chars)
    permutation = {orig: to for orig, to in zip(original_chars, chars)}
#     for orig, to in zip(original_chars, chars):
#         print(f'replacing {orig} -> {to}')
    return ''.join(permutation[c] for c in sample), permutation

def unpermutate(permutated_text, permutation):
    inversed_index = {v:k for k,v in permutation.items()}
    return ''.join(inversed_index[c] for c in permutated_text)

def freq_to_sorted_list(freq: Dict):
    return sorted([(k,v) for k,v in freq.items()], key=lambda x: -x[-1])

def plot_accuracy(x, y, title, window):
    fig = px.scatter(x=x, y=y, title=title,
                 labels={'x': 'length of sample', 'y': 'accuracy'})
    sums, counts = defaultdict(float), defaultdict(int)
    for xi, yi in zip(x, y):
        x_key = xi // window * window
        sums[x_key] += yi
        counts[x_key] += 1
    mean_x = sorted(sums.keys())
    fig.add_scatter(x=mean_x, y=[sums[xi]/counts[xi] for xi in mean_x], name='mean line', opacity=0.7, )
    return fig

def try_decode(encoded, guess):
    return ''.join(guess[c] for c in encoded)

1. Базовый частотный анализ

• подсчитайте частоты букв по корпусам (пунктуацию и капитализацию можно просто опустить, а вот пробелы лучше оставить);
• возьмите какие-нибудь тестовые тексты (нужно взять по меньшей мере 2-3 предложения, иначе вряд ли сработает), зашифруйте их посредством случайной перестановки символов;
• расшифруйте их таким частотным методом.

print(f"Example of cleared text:\n\t{clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)[:400]}")
wap_corpus = read_corpus('WarAndPeace.txt', cyrillic_alphabet)
fig = px.histogram(corpus_to_df(wap_corpus), x='char', y='count', 
                    labels={'count':'char count'}, 
                    title='Chars distribution')
py.iplot(fig)

Example of cleared text:
	война и мир  самый известный роман льва николаевича толстого как никакое другое произведение писателя отражает глубину его мироощущения и философииэта книга из разряда вечных потому что она обо всем  о жизни и смерти о любви и чести о мужестве и героизме о славе и подвиге о войне и мирепервый том знакомит с высшим обществом россии  века показаны взаимоотношения между родителями и детьми в семье ро

def try_decode_1gram(sample, corpus):
    sample_freq = count_n_grams(sample, n=1)
    sample_freq = freq_to_sorted_list(sample_freq)
    corpus_freq = freq_to_sorted_list(corpus)
    inverted_index = {}
    for sc, cc in zip(sample_freq, corpus_freq):
        from_c, _ = sc
        to_c, _ = cc
        inverted_index[from_c] = to_c
#         print(f'encoding {from_c} -> {to_c}')
    return ''.join(inverted_index[c] for c in sample)

def char_accuracy(s1, s2):
    total = 0
    equal = 0
    for c1, c2 in zip(s1, s2):
        total += 1
        equal += c1 == c2
    return 100.0 * equal / total

debug_output = False
x, y = [], []
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
                           min_len=100, max_len=1000, number_of_samples=1000)
for sample in samples:
    encoded, permutation = permutate(sample)
    decoded = try_decode_1gram(encoded, wap_corpus)
    acc = char_accuracy(sample, decoded)
    x.append(len(sample))
    y.append(acc)
    if debug_output:
        print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
        print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='One-gram frequency analysis', window=10)
py.iplot(fig)

2. Частотный метод с использованием биграмм

bigrams = read_corpus('WarAndPeace.txt', cyrillic_alphabet, n_gram_size=2, add_space=False)
sorted_cyrrilic_abc = sorted(list(cyrillic_alphabet))
bigrams_dist = np.zeros((len(sorted_cyrrilic_abc), len(sorted_cyrrilic_abc)))
for i, a in enumerate(sorted_cyrrilic_abc):
    for j, b in enumerate(sorted_cyrrilic_abc):
        bigrams_dist[i][j] = bigrams.get(a + b, 0.0)
        
print(f'Most common bigrams: {bigrams.most_common(10)}')
fig = px.imshow(
    bigrams_dist,
    labels=dict(x="Second letter", y="First letter", color="Couccurance"),
    x=sorted_cyrrilic_abc,
    y=sorted_cyrrilic_abc,
    title="Bigrams distribution"
)
py.iplot(fig)

Most common bigrams: [('то', 8663), ('ст', 6846), ('на', 6585), ('ов', 6487), ('ал', 5857), ('го', 5802), ('он', 5621), ('не', 5581), ('но', 5542), ('ко', 5494)]

most_frequent_bigrams = bigrams.most_common(100)
fig = px.histogram(
    x=[i[0] for i in most_frequent_bigrams], 
    y=[i[1] for i in most_frequent_bigrams],
    labels={'x': 'bigrams', 'y': 'count'},
    title='100 most common bigrams'
)
py.iplot(fig)

Поискав в Интеренете, про биграммный поиск пишут, что он просто аналогичен обычному. Тем не менее, у меня не сложилось четкого понимания, как декодировать с помощью биграмм. Очевидно, мы считаем частоту совстречаемости пар символов. Однако, дальше возникает вопрос, что делать.

Например, вот у нас в закодированной последовательности встречается такая комбинация: $$a_{t-1} a_t a_{t+1} a_{t+2}$$ Пусть мы знаем, что среди них $a_t a_{t+1}$ являются самой частой парой, и в соответствии с корпусом, мы им назначаем пару $b_t b_{t+1}$. Дальше возникает вопрос, как действовать. Например, пара $a_{t-1} a_t$ является следующей по частоте встречаемости, но ей соответсвует (по частоте в корпусе), пара $c_{t-1} c_{t}$, при чем $c_t \neq b_t$

Как поступать в таком случае?

В реализованном ниже примере используется следующий подход: мы выбираем наиболее вероятную пару из допустимых. То есть, в данном случае, мы наложим ограничение на выбор $c_{t} \equiv b_{t}$. Это позволяет однозначным образом декодировать. Недостатком является накапливание ошибки: если мы плохо декодировали самую вероятную пару, то дальше алгоритм уже не выправится.

class BiGramDecoder:
    def __init__(self, alphabet, corpus_text):
        self.alphabet = set(alphabet)
        self.corpus_freq = count_n_grams(corpus_text, n=2)
        self.corpus_freq_list = freq_to_sorted_list(self.corpus_freq)
        self.already_processed = {}

    def _decode(self, a, b):
        if a in self.already_processed and b in self.already_processed:
            return self.already_processed[a], self.already_processed[b]
        elif a in self.already_processed:
            best_p = -1.0
            best_c = None
            decoded_a = self.already_processed[a]
            for c in self.alphabet - set(self.already_processed.values()):
                if self.corpus_freq[decoded_a + c] > best_p:
                    best_p = self.corpus_freq[decoded_a + c]
                    best_c = c
            self.already_processed[b] = c
            return decoded_a, c
        elif b in self.already_processed:
            best_p = -1.0
            best_c = None
            decoded_b = self.already_processed[b]
            for c in self.alphabet - set(self.already_processed.values()):
                if self.corpus_freq[c + decoded_b] > best_p:
                    best_p = self.corpus_freq[c + decoded_b]
                    best_c = c
            self.already_processed[a] = c
            return c, decoded_b
        else:
            used = set(self.already_processed.values())
            for seq, _ in self.corpus_freq_list:
                c, d = seq
                if c not in used and d not in used:
                    self.already_processed[a] = c
                    self.already_processed[b] = d
                    return c, d
        
    def __call__(self, sample):
        assert len(self.already_processed) == 0
        sample_freq = freq_to_sorted_list(count_n_grams(sample, n=2))
        letters_in_sample = len(set(sample))
        for seq, cnt in sample_freq:
            a, b = self._decode(seq[0], seq[1])
#             print(f'{seq}[{cnt}] -> {a}{b}')
            if len(self.already_processed) == letters_in_sample:
                break
#         print(self.already_processed)
#         print(sample)
        return ''.join(self.already_processed[c] for c in sample)
    
    def reset(self):
        self.already_processed = {}

debug_output = False
x, y = [], []
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet, add_space=False)
decoder = BiGramDecoder(cyrillic_alphabet, corpus_text)

samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet, add_space=False,
                           min_len=200, max_len=2000, number_of_samples=1000)
for sample in samples:
    encoded, permutation = permutate(sample)
    decoder.reset()
    decoded = decoder(encoded)
    acc = char_accuracy(sample, decoded)
    x.append(len(sample))
    y.append(acc)
    if debug_output:
        print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
        print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='Bi-gram frequency analysis', window=20)
py.iplot(fig)

Как видно, результат получился очень неустойчивым, и в среднем хуже, чем для униграмм.

Будем исходить из предположение, что частота встречаемости биграмм распределена нормально со средним, посчитанным по корпусу и некоторой дисперсией (которую как раз подберем по MCMC-алгоритму, смотря на количество принятых/отброшенных сэмплов). Тогда мы сможем определить вероятность встретить биграмму с такой частотой в примере по функцию нормального распределения: $$p(ab) = f(freq_{ab}, N(mu_{ab}, std))$$ где $freq_{ab}$ - частота пары $ab$ в примере, $mu_{ab}$ - частота пары $ab$ на корпусе

И в итоге можно получить вероятность данной перестановки путем произведенеия вероятностей для каждой из биграмм

def get_log_proba(prediction, sample_pairs, corpus_pairs, std):
    MIN_RATIO = 1e-6
    res = 0
#     print(f'get_log_proba->{sample_pairs}')
    for s_pair, x in sample_pairs.items():
        c_pair = prediction[s_pair[0]] + prediction[s_pair[1]]
        mu = corpus_pairs.get(c_pair, MIN_RATIO)
#         print(s_pair, x, mu, norm.logpdf(x, mu, std))
        res += norm.logpdf(x, mu, std)
    return res # np.exp(res)

3. Биграммный анализ с использованием MCMC алгоритма

Сделаем MCMC алгоритм. В качестве отдельного шага будем менять буквы в перестановке, и смотреть, как это отразится на итоговой вероятности перестановки. Выбор букв для замены будем делать равновероятным (то есть распределение для сэмплирование $q(x^{t+1}|x^t)$ - получается симметричным).

Тогда алгоритм следующий:

1. выбираем произвольную начальную перестановку $x^0$
2. меняем в перестановке $x^i$ две буквы и получаем $x^{i+1}$
3. считаем $p(x^i)$, $p(x^{i+1})$ и $a(x^i, x^{i+1}) = \frac{p(x^{i+1})}{(x^i)}$
4. если $a(x^i, x^{i+1}) >= 1$, то принимаем $x^{i+1}$ и переходим к следующему шагу (с пункта 2)
5. если $a(x^i, x^{i+1}) < 1$, то принимаем $x^{i+1}$ с вероятностью $a(x^i, x^{i+1})$ (иначе оставляем $x^i$) и переходим к следующему шагу (с пункта 2)

class MCMC:
    def __init__(self, corpus_text, std):
        corpus = count_n_grams(corpus_text, n=2)
        total = sum(corpus.values())
        self.corpus_chars = count_n_grams(corpus_text, n=1)
        self.corpus_pairs = {key: value/total for key, value in corpus.items()}
        self.std = std
        
    def make_n_steps(self, sample_text, n, initial_x=None):
        sample_pairs = count_n_grams(sample_text, n=2)
        sample_total = sum(sample_pairs.values())
        sample_pairs = {key: value/sample_total for key, value in sample_pairs.items()}
#         print(f"initial_x: {initial_x}")
        
        chars = list(set(sample_text))
        if initial_x is not None:
            x = initial_x.copy()
            p_cur = get_log_proba(initial_x, sample_pairs, self.corpus_pairs, self.std)
            p_next = get_log_proba(x, sample_pairs, self.corpus_pairs, self.std)
#             print(f'Set initial state, starts from , {p_cur} <-> {p_next}')
        else:
            temp = [p[0] for p in self.corpus_chars.most_common(len(chars))]
            np.random.shuffle(temp)
            x = {c:to_c for c, to_c in zip(chars, temp)}
        hist = []
        accepted_count = 0
        accepted_negative = 0
        below = 0
        for i in tqdm(range(n)):
            a, b = np.random.choice(chars, 2, False)
            x_next = x.copy()
            x_next[a], x_next[b] = x_next[b], x_next[a]
#             print(f'step_{i}, {a, b, x[b], x[a]}, {get_proba(x, sample_pairs, self.corpus_pairs, self.std)}')
            p_cur = get_log_proba(x, sample_pairs, self.corpus_pairs, self.std)
            p_next = get_log_proba(x_next, sample_pairs, self.corpus_pairs, self.std)
            hist.append(p_cur)
            
            a = p_next - p_cur
            below += a < 0
#             print(f'a={a}, p_next={p_next}, p_cur={p_cur}')
            if a >= 0:
                x = x_next
                accepted_count += 1
            else:
                if np.random.random() < np.exp(a):
                    x = x_next
                    accepted_count += 1
                    accepted_negative += 1
        print(f'Total steps: {n}, accepted={accepted_count} ({100.0*accepted_count/n}%),',
              f'below_zero={below}, accepted_negative={accepted_negative}')
        hist.append(get_log_proba(x, sample_pairs, self.corpus_pairs, self.std))
        return x, hist, 100.0*accepted_count/n
            

Подберем значение стандартного отклонения в нормальном распределении так, чтоб число принятых было на уровне 0.5

corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
                           min_len=100, max_len=1000, number_of_samples=5)
std_candidates = np.linspace(0.0001, 0.01, 40)
accepted_hist = []
for std in std_candidates:
    print(f'std={std}')
    sum_accepted = 0
    mcmc = MCMC(corpus_text, std)
    for sample in samples:
        x, hist, accepted_ratio = mcmc.make_n_steps(sample, 500)
        sum_accepted += accepted_ratio
        clear_output()
    accepted_hist.append(sum_accepted / len(samples))

fig = px.line(x=std_candidates, y=accepted_hist, title='Selecting std for gaus-dist (in MCMC)',
              labels={'x': 'std', 'y': 'mean accepted ratio'})
py.iplot(fig)

Для более точного предсказания предлагается также сделать двухэтапную схему: сначала выходим на плато (по $p(X_{permutation})$), а затем понижаем STD, чтоб брать отбирать только наиболее вероятные перестановки. Ниже показан пример, как зависит точность предсказания от понижение std (каждую эпоху снижаем в два раза)

corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
sample_text = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
                               min_len=300, max_len=1000, number_of_samples=1)[0]

std = 0.1
decrease_count = 20
mcmc = MCMC(corpus_text, std=std)
accuracy_hist = []
accepted_hist = []
std_hist = []
hist = []
x0 = None
for i in range(decrease_count):
    clear_output()
    mcmc.std = std
    std_hist.append(std)
    x0, hist_cur, accepted_ratio = mcmc.make_n_steps(sample_text, 5000, x0)
    hist += hist_cur
    decoded = ''.join(x0[c] for c in sample_text)
    acc = char_accuracy(sample_text, decoded)
    accuracy_hist.append(acc)
    accepted_hist.append(accepted_ratio)
    print(f"Done {i+1} for std={std}")
    std = std / 2

fig = make_subplots(
    rows=3, cols=2,
    specs=[[{"colspan": 2}, {}],
           [{"colspan": 2}, {}],
           [{}, {}]],
    subplot_titles=("Score proportional the probability of permutation based on bigrams distribution", None,
                    "Accuracy of decoding", None,
                    "STD decline through epoch", 
                    "Percent of accepted samples"),
)

fig.add_trace(go.Scatter(x=np.arange(len(hist)), y=hist, ),
                 row=1, col=1)

fig.add_trace(go.Scatter(x=np.arange(len(accuracy_hist)), y=accuracy_hist),
                 row=2, col=1)
fig.add_trace(go.Scatter(x=np.arange(len(std_hist)), y=std_hist),
                 row=3, col=1)
fig.add_trace(go.Scatter(x=np.arange(len(accepted_hist)), y=accepted_hist),
                 row=3, col=2)

fig.update_layout(showlegend=False, title_text="Decreasing std through epochs", height=1200)
py.iplot(fig)

100%|██████████| 5000/5000 [04:00<00:00, 20.78it/s]

Total steps: 5000, accepted=0 (0.0%), below_zero=5000, accepted_negative=0
Done 20 for std=1.9073486328125e-07

STD=0.008

corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
                           min_len=100, max_len=1000, number_of_samples=10)
mcmc = MCMC(corpus_text, std=STD)
hist_by_sample = []
steps_number = 3000
for i, sample in enumerate(samples):
    _, hist, _ = mcmc.make_n_steps(sample, steps_number)
    hist_by_sample.append(hist)
    clear_output()
    print(f"Done {i+1}/{len(samples)}")

Done 10/10

x = np.arange(len(hist_by_sample[0]))

fig = px.line(x=x, y=hist_by_sample[0], 
              labels={"x": "steps", "y": "function that is proportinal to probability"},
             title="Number of steps for convergence")
for hist in hist_by_sample[1:]:
    fig.add_scatter(x=x, y=hist)
py.iplot(fig)

В целом видно, что 1000 шагов хватает для того, чтоб MCMC вышел на плато. Будем выполнять эти шаги перед началом семплирования

INITIAL_STEPS = 1000

corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
                           min_len=100, max_len=1000, number_of_samples=40)
samples = sorted(samples, key=len)
mcmc = MCMC(corpus_text, std=STD)

samples_per_text = 10
samples_len = []
samples_acc = []
all_log = []
for sample in samples:
    encoded, permutation = permutate(sample)
    mcmc.std = STD
    x, _, _ = mcmc.make_n_steps(encoded, INITIAL_STEPS)
    mcmc.std /= 2
    sample_accuracy = 0
    for _ in range(samples_per_text):
        res = mcmc.make_n_steps(encoded, np.random.randint(20, 100), initial_x=x)
        x, _, _ = res
        decoded = ''.join(x[c] for c in encoded)
        acc = char_accuracy(sample, decoded)
        all_log.append({
            'sample': sample, 
            'encoded': encoded, 
            'permutation': permutation, 
            'res': res, 
            'acc': acc
        })
        sample_accuracy += acc
    samples_len.append(len(sample))
    samples_acc.append(sample_accuracy / samples_per_text)
clear_output()

Пример успешного декодирования методом MCMC:

# all_log1 = all_log
best_decoding = np.argmax([x['acc'] for x in all_log])
best = all_log[best_decoding]
print(f'Original sample:\n\t{best["sample"]}')
print(f'Ecoded sample:\n\t{best["encoded"]}')
guessed_permutation = best['res'][0]
decoded = ''.join(guessed_permutation[c] for c in best['encoded'])
print(f'Decoded sample:\n\t{decoded}')
print(f'Accuracy: {best["acc"]}%')

Original sample:
	 кити не рассердись но ты подумай дело это так важно что мне больно думать что ты смешиваешь чувство слабости нежелания остаться одной ну тебе скучно будет одной ну поезжай в москву
Ecoded sample:
	етш шеякеучжжкуишжлеясе вепсирычдеикьсеэ се чтеачйясез сеыякемсьлясеирыч лез се вежыкншачкнлезраж асежьчмсж шеякйкьчяшбесж ч лжбесиясдеяре кмкежтрзясемрик есиясдеярепскойчдеаеысжтар
Decoded sample:
	 лити не массемдись но ты годукая деро бто тал вазно что кне порьно дукать что ты скеживаежь чувство срапости незераний остатьсй одноя ну тепе случно пудет одноя ну гоешзая в кослву
Accuracy: 81.21546961325967%

fig = px.line(x=samples_len, y=samples_acc, title='Accuracy', labels={'x': 'sample length', 'y': 'accuracy'})
py.iplot(fig)

4. Распаковка "пляшущих человечков"

encoded = "←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏"
print (encoded)

←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏

encoded_freq = count_n_grams(encoded, 1)

most_frequent_unigrams = encoded_freq.most_common(100)
fig = px.histogram(
    x=[i[0] for i in most_frequent_unigrams], 
    y=[i[1] for i in most_frequent_unigrams],
    labels={'x': 'char', 'y': 'count'},
    title='Frequence of chars'
)
py.iplot(fig)

encoded_bifreq = count_n_grams(encoded, 2)
most_frequent_bigrams = encoded_bifreq.most_common(100)
fig = px.histogram(
    x=[i[0] for i in most_frequent_bigrams], 
    y=[i[1] for i in most_frequent_bigrams],
    labels={'x': 'bigram', 'y': 'count'},
    title='Frequence of bigrams (100 most frequent)'
)
py.iplot(fig)

corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
mcmc = MCMC(corpus_text, std=STD)
guess, hist, accepted_ratio = mcmc.make_n_steps(encoded, INITIAL_STEPS)

fig = px.line(x=np.arange(len(hist)), y=hist, 
              labels={"x": "steps", "y": "function that is proportinal to probability"},
              title="Convergence of MCMC")
py.iplot(fig)

100%|██████████| 1000/1000 [00:30<00:00, 32.62it/s]

Total steps: 1000, accepted=465 (46.5%), below_zero=769, accepted_negative=234

def replace_chars(to_replace, guess):
    inverted_index = {v: k for k,v in guess.items()}
    for from_char, to_char in to_replace.items():
        if to_char in inverted_index:
            inverted_index[from_char], inverted_index[to_char] = inverted_index[to_char], inverted_index[from_char]
        else:
            inverted_index[to_char] = inverted_index[from_char]
            del inverted_index[from_char]
    return {v: k for k,v in inverted_index.items()}

best = -1000
best_x = None
# x = guess
improved = 0
mcmc.std = STD
hypotheses = []
for _ in range(100):
    clear_output(True)
    x, h, _ = mcmc.make_n_steps(encoded, 20, x)
    hypotheses.append(x)
    if h[-1] > best:
        best = h[-1]
        best_x = x
        improved += 1
clear_output(True)
print(f'Number of improve: {improved}')

Number of improve: 6

Первые два слова очень похожи на "если вы". Попробуем заменить их. и далее раскрутить

guess = hypotheses[5]
print(f"Originally guess: {guess}")
print(f"Originally: {try_decode(encoded, guess)}")
guess = replace_chars({'и': 'с', 'р': 'л', 'а': 'и', 'ю': 'д'}, guess)
guess = replace_chars({'ю': 'т', 'м': 'п', 'к': 'ч'}, guess)
guess = replace_chars({'н': 'к', 'а': 'р', 'я': 'й'}, guess)
guess = replace_chars({'м': 'н', 'ь': 'а', 'у': 'ь', 'я': 'б', 'ю': 'з', 'ш': 'х', }, guess)
guess = replace_chars({'ж': 'я'}, guess)
guess = replace_chars({'ж': 'э', 'у': 'щ', 'ю': 'у'}, guess)

print(f"Guess: {guess}")
# print(f"Encoded: {encoded}")
print(f"Decoded: {try_decode(encoded, guess)}")

Originally guess: {'⇙': 'з', '↝': 'п', '⇈': 'у', '⇠': 'и', '←': 'е', '↞': 'ж', '⇴': 'ь', '⇰': 'т', '⇛': 'о', '↨': 'д', '↟': 'а', '↹': ' ', '↷': 'в', '⇷': 'м', '⇆': 'л', '⇒': 'р', '↘': 'ш', '⇞': 'к', '↾': 'я', '↤': 'ю', '⇊': 'ы', '⇸': 'б', '↲': 'й', '↳': 'ч', '⇌': 'н', '↙': 'г', '⇏': 'х', '⇯': 'с'}
Originally: еира вы ваюаде посчьрупыя ара мокда посчьрупыя денид з бдого иоойлепаж нодосыя регно мсокадьду иносее виего вы вие июерьра мсьварупо а морзкаде чьниачьрупыя йьрр ть моиреюпее кедвесдое тьюьпае нзсиь шодж нопекпо ж пакего пе ойельх
Guess: {'⇰': 'з', '⇷': 'п', '↟': 'и', '←': 'е', '⇈': 'ь', '↨': 'т', '⇛': 'о', '↤': 'д', '⇴': 'а', '↹': ' ', '↷': 'в', '↳': 'м', '⇒': 'л', '⇯': 'р', '⇏': 'ш', '⇌': 'к', '↞': 'я', '⇊': 'ы', '↲': 'б', '↾': 'й', '⇞': 'ч', '↝': 'н', '↙': 'г', '↘': 'х', '⇠': 'с', '⇸': 'э', '⇆': 'щ', '⇙': 'у'}
Decoded: если вы видите нормальный или почти нормальный текст у этого сообщения который легко прочитать скорее всего вы все сделали правильно и получите максимальный балл за последнее четвертое задание курса хотя конечно я ничего не обещаш

Еще некорые получавшиеся гипотезы:

best_x = replace_chars({'к': 'с'}, best_x)
print(f"Decoded: {try_decode(encoded, best_x)}")

Decoded: если кя кишите новбыльняа или подти новбыльняа тегст ю хторо соомжениу готовяа лерго пводитыть сговее ксеро кя ксе сшелыли пвыкильно и полюдите быгсибыльняа мылл чы послешнее деткевтое чышыние гювсы зоту гонедно у нидеро не омежый

best_x = replace_chars({'я': 'ы'}, best_x)
print(f"Guess: {best_x}")
print(f"Encoded: {encoded}")
print(f"Decoded: {try_decode(encoded, best_x)}")

Guess: {'⇙': 'ю', '↝': 'н', '⇈': 'ь', '⇷': 'к', '←': 'е', '↞': 'у', '⇊': 'ы', '⇰': 'ч', '⇛': 'о', '↷': 'т', '↟': 'и', '↹': ' ', '⇠': 'с', '↨': 'п', '⇆': 'ж', '⇒': 'л', '↘': 'з', '⇞': 'д', '↾': 'а', '↤': 'ш', '⇴': 'я', '⇸': 'х', '↲': 'м', '↳': 'б', '⇌': 'г', '↙': 'р', '⇏': 'й', '⇯': 'в'}
Encoded: ←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏
Decoded: если ты тишипе новбяльныа или кодпи новбяльныа пегсп ю хпоро соомжениу гоповыа лерго кводипяпь сговее тсеро ты тсе сшеляли квятильно и колюдипе бягсибяльныа мялл чя кослешнее дептевпое чяшяние гювся зопу гонедно у нидеро не омежяй